#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *pNext; // pNext是结构体类型的指针变量
} NODE, *PNODE;         // PNODE <==> struct Node {...} *

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
} STACK, *PSTACK;

/*
函数声明
*/
void init(PSTACK);
void push(PSTACK, int);
void traverse(PSTACK);
bool pop(PSTACK, int *);
bool empty(PSTACK pS);
void clear(PSTACK);

/*
主函数
*/
int main(void)
{
    STACK S; //等价于struct Stack
    int val;

    init(&S);    //初始化：发送S的地址才能改变S的值
    push(&S, 1); //压栈
    push(&S, 2);
    push(&S, 3);
    traverse(&S); //遍历输出

    if (pop(&S, &val)) //指定哪个栈进行出栈，保存出栈的元素
    {
        printf("出栈成功，出栈的元素为：%d\n", val);
    }
    else
    {
        printf("出栈失败！\n");
    }

    clear(&S);
    traverse(&S);

    return 0;
}

/*
初始化一个栈
*/
void init(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if (NULL == pS->pTop)
    {
        printf("动态内存分配失败\n");
        exit(-1);
    }
    else
    {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL;
    }
}

/*
压栈
*/
void push(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;
    pNew->pNext = pS->pTop; // pS->pTop不能改成pS->pBottom
    pS->pTop = pNew;
    return;
}

/*
遍历栈
*/
void traverse(PSTACK pS)
{
    PNODE p = pS->pTop;
    while (p != pS->pBottom)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
    return;
}

/*
出栈：把pS所指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中，如果出栈成功返回true
*/
bool pop(PSTACK pS, int *pVal)
{
    if (empty(pS))
    { // pS本身存放的就是栈S的地址
        return false;
    }
    else
    {
        PNODE r = pS->pTop;
        *pVal = r->data;
        pS->pTop = r->pNext;
        free(r);
        r = NULL;

        return true;
    }
}

/*
判断栈是否为空
*/
bool empty(PSTACK pS)
{
    if (pS->pTop == pS->pBottom)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/*
清空一个栈
*/
void clear(PSTACK pS)
{
    if (empty(pS))
    {
        return;
    }
    else
    {
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while (p != pS->pBottom)
        {
            q = p->pNext;
            free(p);
            p = q;
        }
    }
    pS->pTop = pS->pBottom;
    return;
}

/*
输出内容：
3 2 1
出栈成功，出栈的元素为：3

*/